/**
 * kruscal 算法来生成最小生成树
 * 同样也是利用切分性质进行贪心选择
 * 
 * 算法思路：
 *      将 n 个顶点看作是 n 个孤立的联通分支，将图中所有的边按照从小到大排序。
 *      然后从第一条边开始，依照边的权重递增的顺序查看每一条边，并按下述方法连接两个不同的联通分支：
 *      查看第K(i, j)条边时，假如 i 和 j 是属于两个不同的联通分支T1, T2的顶点时，就用（i, j）把
 *      T1, T2连接成一个联通分支；如果 i 和 j 是属于同一个联通分支的顶点时，则直接跳过，去处理 k + 1条边；
 *      直到只剩一个联通分支时处理结束
 *      
 * 根据上述算法思路，可以分析出我们要做的内容：
 * 1：如何对 图的边存储并进行递增的排序？ --- 可以采用任何一种排序方法
 * 2：如何判断边的两个顶点是否在同一个联通分支中？  --- 并查集（参考资料：https://blog.csdn.net/mgsky1/article/details/77840286）  
 */

 // 边集中的元素节点
class EdgesNode {
    constructor(pre, bak, weight) {
        this.pre = pre
        this.bak = bak
        this.weight = weight
    }
}

// 边集
class Edges {
    constructor(g) {
        // 提取出图中的边（假设为）
        const edges = []
        for (let j = 0; j < g.length - 1; j++) {
            for (let i = 0; i < g[j].length; i++) {
                if (g[j][i] !== 0 && g[j][i] !== 100000) {
                    edges.push(new EdgesNode(j, i, g[j][i]))
                }
            }
        }
        // 对边进行递增排序
        this.edges = this.bubleSort(edges)
    }
    bubleSort(data) {
        let i, j = data.length - 1, t, lastIndex
        while(j > 0) {
            lastIndex = 0
            for (i = 0; i < j; i++) {
                if (data[i].weight > data[i + 1].weight) {
                    t = data[i]
                    data[i] = data[i + 1]
                    data[i + 1] = t
                    lastIndex = i
                }
            }
            j = lastIndex
        }
        return data
    }
}

// 并查集--能够判断节点属于哪一个联通分支中（是否为同一个集合）
class Union {
    /**
     * 根据图来初始化
     * @param {*} g 图
     */
    constructor(g) {
        const data = []
        for (let i = 0; i < g.length - 1; i++) {
            data[i] = i
        }
        this.data = data
    }
    /**
     * 寻找顶点的根
     * @param {*} v 顶点在邻接矩阵中的下标
     */
    findRoot(v) {
        while (this.data[v] != v) {
            v = this.data[v]
        }
        return v
    }
}

/**
 * 生成最小生成树
 * @param {*} p 邻接矩阵存储的图p g
 */
function kruskal(g) {
    const edges = new Edges(g).edges // 初始化边集
    const union = new Union(g) // 初始化并查集
    for (let item of edges) {
        let preRoot = union.findRoot(item.pre)
        let bakRoot = union.findRoot(item.bak)
        if (preRoot != bakRoot) { // 两个节点的根节点不同，代表不同源，加入到最小生成树当中
            console.log(`edge: (${item.pre}, ${item.bak}), weight: ${item.weight}`)
            union.data[preRoot] = bakRoot // 修改前者的根（preRoot）在查并级中位置的值为后者的根（bakRoot）
        }
    }
}


